An analysis of reduced Hessian methods for constrained optimization

We study the convergence properties of reduced Hessian successive quadratic programming for equality constrained optimization. The method uses a backtracking line search, and updates an approximation to the reduced Hessian of the Lagrangian by means of the BFGS formula. Two merit functions are considered for the line search: the ₁ function and the Fletcher exact penalty function. We give conditions under which local and superlinear convergence is obtained, and also prove a global convergence result. The analysis allows the initial reduced Hessian approximation to be any positive definite matrix, and does not assume that the iterates converge, or that the matrices are bounded. The effects of a second order correction step, a watchdog procedure and of the choice of null space basis are considered. This work can be seen as an extension to reduced Hessian methods of the well known results of Powell (1976) for unconstrained optimization.This author was supported, in part, by National Science Foundation grant CCR-8702403, Air Force Office of Scientific Research grant AFOSR-85-0251, and Army Research Office contract DAAL03-88-K-0086.This author was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under contracts W-31-109-Eng-38 and DE FG02-87ER25047, and by National Science Foundation Grant No. DCR-86-02071.     

On random walks arising in queueing systems: ergodicity and transience via quadratic forms as lyapounov functions — Part I

A simple and quite general approach is proposed to derive criteria for transience and ergodicity of a certain class of irreducibleN-dimensional Markov chains in ₊ ^N assuming a boundedness condition on the second moment of the jumps. The method consists in constructing convenient smooth supermartingales outside some compact set. The Lyapounov functions introduced belong to the set of quadratic forms in ₊ ^N and do not always have a definite sign. Existence and construction of these forms is shown to be basically equivalent to finding vectors satisfying a system of linear inequalities.Part I is restricted toN=2, in which case a complete characterization is obtained for the type of random walks analyzed by Malyshev and Mensikov, thus relaxing their condition of boundedness of the jumps. The motivation for this work is partly from a large class of queueing systems that give rise to random walks in ₊ ^N      

A minimum average risk approach to shrinkage estimators of the normal mean

For the problem of estimating the normal mean based on a random sample X ₁,...,X _n when a prior value ₀ is available, a class of shrinkage estimators % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-qqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xHapdbiqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaubeaeqaje% aWbaGaamOBaaWcbeqdbaGafqiVd0MbaKaaaaGccaqGGaGaaiikaiaa% dUgacaGGPaGaeyypa0Jaam4AaiaacIcadaqfqaqabKqaahaacaqGUb% aaleqaneaacaqGubaaaOGaaiykaiaabccadaqfqaqabKqaahaacaWG% UbaaleqaneaaceqGybGbaebaaaGccaqGGaGaey4kaSIaaeiiaiaacI% cacaaIXaGaaeiiaiabgkHiTiaabccacaWGRbGaaiikamaavababeqc% baCaaiaab6gaaSqab0qaaiaabsfaaaGccaGGPaGaaiykamaavababe% qcbaCaaiaad6gaaSqab0qaaiabeY7aTbaaaaa!5615!\[\mathop {\hat \mu }\nolimits_n {\rm{ }}(k) = k(\mathop {\rm{T}}\nolimits_{\rm{n}} ){\rm{ }}\mathop {{\rm{\bar X}}}\nolimits_n {\rm{ }} + {\rm{ }}(1{\rm{ }} - {\rm{ }}k(\mathop {\rm{T}}\nolimits_{\rm{n}} ))\mathop \mu \nolimits_n \] is considered, where % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-qqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xHapdbiqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaubeaeqaje% aWbaGaamOBaaWcbeqcdawaaiaadsfaaaGccaqGGaGaaeypaiaabcca% caWGUbWaaWbaaSqabeaacaaIXaGaai4laiaaikdaaaGccaGGOaWaa0% aaaeaacaWGybaaamaaBaaajeaWbaGaamOBaaWcbeaakiaabccacqGH% sislcaqGGaWaaubeaeqajeaWbaGaaGimaaWcbeqdbaGaaeiVdaaaki% aacMcacaqGGaGaae4laiabeccaGiabeo8aZbaa!4C33!\[\mathop T\nolimits_n {\rm{ = }}n^{1/2} (\overline X _n {\rm{ }} - {\rm{ }}\mathop {\rm{\mu }}\nolimits_0 ){\rm{ /}} \sigma \] and k is a weight function. For certain choices of k, % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-qqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xHapdbiqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaubeaeqaje% aWbaGaamOBaaWcbeqdbaGafqiVd0MbaKaaaaGccaqGGaGaaiikaiaa% dUgacaGGPaaaaa!3CEE!\[\mathop {\hat \mu }\nolimits_n {\rm{ }}(k)\] coincides with previously studied preliminary test and shrinkage estimators. We consider choosing k from a natural non-parametric family of weight functions so as to minimize average risk relative to a specified prior p. We study how, by varying p, the MSE efficiency (relative to \-X) properties of % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-qqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xHapdbiqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaubeaeqaje% aWbaGaamOBaaWcbeqdbaGafqiVd0MbaKaaaaGccaqGGaGaaiikaiaa% dUgacaGGPaaaaa!3CEE!\[\mathop {\hat \mu }\nolimits_n {\rm{ }}(k)\] can be controlled. In the process, a certain robustness property of the usual family of posterior mean estimators, corresponding to the conjugate normal priors, is observed.     

Decomposition of multiattribute expected-utility functions

This paper integrates and extends the theory of the decomposition of multiattribute expected-utility functions based on utility independence. In a preliminary section, the standard decision model of expected utility is briefly discussed, including the fact that the decision maker's preference forlotteries with two outcomes determines the utility function uniquely. The decomposition possibilities of a utility function are captured by the concept ofautonomous sets of attributes, an affine separability of some kind known as generalized utility independence.Overlapping autonomous sets lead to biaffine-associative, i.e.multiplicative oradditive decompositions. The multiplicative representation shows that autonomy has strongerclosure properties than utility independence, for instance with respect to set-theoretic difference. Autonomy is also a concept with a wider scope since it applies to the decomposition of Boolean functions, games and a number of other topics in combinatorial optimization. This relationship to the well-known theory ofsubstitution decomposition in discrete mathematics also reveals a kind of discrete core behind the decomposition of utility functions. The entirety of autonomous sets can be represented by a compact data structure, the so-calledcomposition tree, which frequently corresponds to a natural hierarchy of attributes. Multiplicative/additive ormulti-affine functions correspond to the hierarchy steps. The known representation of multi-affine functions is shown to be given by aMoebius inversion formula. The entire approach has the advantage that it allows the application of more sophisticated representation methods on a detailed level, whereas it employs onlyfinite set theory andarithmetic on the main levels in the hierarchy.     

Convex programs with an additional reverse convex constraint

A method is presented for solving a class of global optimization problems of the form (P): minimizef(x), subject toxD,g(x)0, whereD is a closed convex subset ofR ⁿ andf,g are convex finite functionsR ⁿ . Under suitable stability hypotheses, it is shown that a feasible point is optimal if and only if 0=max{g(x):xD,f(x)f( )}. On the basis of this optimality criterion, the problem is reduced to a sequence of subproblemsQ _k ,k=1, 2, ..., each of which consists in maximizing the convex functiong(x) over some polyhedronS _k . The method is similar to the outer approximation method for maximizing a convex function over a compact convex set.     

Quadratic Padé approximants and the intruder state problem of multireference perturbation methods

Simple and quadratic Padé resummation methods are applied to high‐order series from multireference many‐body perturbation theory (MR‐MBPT) calculations using various partitioning schemes (Møller–Plesset, Epstein–Nesbet, and forced degeneracy) to determine their efficacy in resumming slowly convergent or divergent series. The calculations are performed for the ground and low‐lying excited states of (i) CH₂, (ii) BeH₂ at three geometries, and (iii) Be, for which full configuration interaction (CI) calculations are available for comparison. The 49 perturbation series that are analyzed include those with oscillatory and monotonic divergence and convergence, including divergences that arise from either frontdoor or backdoor intruder states. Both the simple and quadratic Padé approximations are found to speed the convergence of slowly convergent or divergent series. However, the quadratic Padé method generally outperforms the simple Padé resummation. © 2005 Wiley Periodicals, Inc. Int J Quantum Chem, 2005     

Preparation and Characterization of N-4-Nitrophenyl-L-prolinol Nanocrystals in Sol-Gel Matrices

Organic nanocrystals of N-4-nitrophenyl-l-prolinol (NPP) have been grown in sol-gel matrices prepared from silicon alkoxide precursors. Our process is based on the control of the nucleation and growth kinetics of the dye in the pores of dense gels. Nanocomposites gel-glasses are obtained with a high optical quality due to the small size of the nanocrystals (10-20 nm). Differential scanning calorimetry experiments evidenced clearly the melting point of NPP nanocrystals, which is registered 51°C above that of NPP powder. Micro-Raman and solid state NMR spectroscopies allowed us to demonstrate that our nanocrystallization process does not chemically modify NPP molecules. We specified also the nature of interactions existing between the NPP nanocrystals and the xerogels. These strong interactions, which explain the important increase of the melting point of the nanocrystals in comparison to the NPP powder, are hydrogen bonds between nitro groups of NPP and uncondensed silanol functions of the silicate network.     

Evaluation of a complete HPLC solvent optimization system involving piece-wise quadratic modelling

Summary Interpretive methods are accepted to give the best possible results for selectivity optimization in HPLC. However the methods are very complex, and most work so far has been detailed academic studies. This paper describes an evaluation of a complete integrated system incorporating peak labelling, modelling of retention behaviour and calculation of response surfaces, with particular emphasis on the retention modelling. The peak labelling section has been discussed previously.A piece-wise quadratic function is investigated for the modelling of retention times across an isoeluotropic plane to effect selectivity optimization in HPLC. This requires 10 data-points on the isoeluotropic plane. The predicted global optimum and local optima are evaluated by comparison of calculated and experimental retention data, for a nine component sample. Seven interstitial points, distributed across the whole plane between the data-points, are similarly evaluated for a related sample. The typical error (in retention time) is less than 2%, often 1%, and the maximum error is 4.2%. At the global optimum the error was found be less than 1.3% for all 9 peaks.     

Competition in the bioreactor with general quadratic yields when one competitor produces a toxin

Microorganisms produce toxins against its competitors sometimes, and variable yields are useful to explain the observed oscillatory behavior in the reactor. In this paper, a model with general quadric yields of competition in the bioreactor of two competitors for a single nutrient where one of the competitors can produce toxin against its opponent, is proposed. We analyze the asymptotic behavior of the model in terms of the relevant parameters. The conditions of the three dimensional Hopf bifurcation, and the existence of limit cycles in the nutrient-organism phase plane are obtained.     

Randomized algorithms for the separation of point sets and for solving quadratic programs

A randomized algorithm for finding a hyperplane separating two finite point sets in the Euclidean space ^d and a randomized algorithm for solving linearly constrained general convex quadratic problems are proposed. The expected running time of the separating algorithm isO(dd! (m + n)), wherem andn are cardinalities of sets to be separated. The expected running time of the algorithm for solving quadratic problems isO(dd! s) wheres is the number of inequality constraints. These algorithms are based on the ideas of Seidel's linear programming algorithm [6]. They are closely related to algorithms of [8], [2], and [9] and belong to an abstract class of algorithms investigated in [1]. The algorithm for solving quadratic problems has some features of the one proposed in [7].This research was done when the author was supported by the Alexander von Humboldt Foundation, Germany.On leave from the Institute of Mathematics and Mechanics, Ural Department of the Russian Academy of Sciences, 620219 Ekaterinburg, S. Kovalevskaya str. 16, Russia.